package com.njupt.graphTheory;

import java.util.*;

/**
 * @Author: wujiaming
 * @CreateTime: 2025/2/4 16:39
 * @Description: 210. 课程表 II 广度优先遍历
 * @Version: 1.0
 */


public class FindOrder_210_bfs {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        //1、构造邻接表和入度数组
        int[] inEdge = new int[numCourses];
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            graph.add(new ArrayList<>());
        }
        for (int[] prerequisite : prerequisites) {
            graph.get(prerequisite[1]).add(prerequisite[0]);
            ++inEdge[prerequisite[0]];
        }
        //2、广度优先遍历实现拓扑排序
        Deque<Integer> queue = new LinkedList<>();
        int[] result = new int[numCourses]; //存放结果集

        //2.1、遍历所有入度为0的节点，将节点放入队列中
        for (int i = 0; i < inEdge.length; i++) {
            if (inEdge[i] == 0) {
                queue.addLast(i);
            }
        }
        int index = 0;
        while (!queue.isEmpty()) {
            //2.2、从队列中取出入度为0 的节点v，将节点v让如结果集中
            Integer v = queue.pollFirst();
            result[index++] = v.intValue();
            for (Integer u : graph.get(v.intValue())) {
                //2.2、对于节点v，将节点v相邻的的节点u入度减1
                inEdge[u.intValue()]--;
                //2.3、如果节点u的入度为0那么就添加到队列中
                if (inEdge[u.intValue()] == 0) {
                    queue.addLast(u);
                }
            }
        }

        if (index != numCourses) {
            return new int[0];
        }
        return result;
    }


    public static void main(String[] args) {
//        int[][] prerequisites = {{0, 1}, {1, 0}};
        int[][] prerequisites = {{1, 0}, {2, 0}, {3, 1}, {3, 2}};
        FindOrder_210_bfs test = new FindOrder_210_bfs();
        int[] order = test.findOrder(4, prerequisites);
        System.out.println(Arrays.toString(order));
    }
}
